#include <cstdio>
#include <cstring>
const int N = 1005;
int n, m;
int map[N][N], f[N][N], dp[N][N];
inline int read() {
	int ch = getchar(), res = 0;
	while (ch > '9' || ch < '0') ch = getchar();
	while (ch <= '9' && ch >= '0') {
		res = (res << 3) + (res << 1) + ch - '0';
		ch = getchar();
	}
	return res;
}
inline int max(int a, int b) { return a > b ? a : b; }
int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
	freopen("testdata.in", "r", stdin);
	freopen("testdata.out", "w", stdout);
#endif
#ifndef LOCAL
	freopen("tree.in", "r", stdin);
	freopen("tree.out", "w", stdout);
#endif
#endif

	n = read(), m = read();
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= i; ++j) { map[i][j] = read(); }
	}
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= i; ++j) { f[i][j] = max(f[i - 1][j], f[i - 1][j - 1]) + map[i][j]; }
	}
	while (m--) {
		int row = read(), col = read();
		if (row == 1 && col == 1) {
			printf("-1\n");
			continue;
		}
		dp[row + 1][col] = f[row][col - 1] + map[row + 1][col],
				 dp[row + 1][col + 1] = f[row][col + 1] + map[row + 1][col + 1];
		for (int i = row + 2; i <= n; ++i) {
			for (int j = col; j <= col + i - row; ++j) {
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]) + map[i][j];
			}
		}
		int ans = 0;
		for (int i = 1; i < col; ++i) { ans = max(ans, f[n][i]); }
		for (int i = col; i <= col + n - row; ++i) { ans = max(ans, dp[n][i]); }
		for (int i = col + n - row + 1; i <= n; ++i) { ans = max(ans, f[n][i]); }
		printf("%d\n", ans);
	}
	return 0;
}